package java_0305_heap_leetcode;

import java.util.*;

/**
 * 求k个和最小的数对
 */
public class Num373_KSmallestPairs {
    private class Pair{
        int u;
        int v;
        public Pair(int u, int v) {
            this.u = u;
            this.v = v;
        }
    }
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        //1.扫描这两个数组，u来自第一个数组，v来自第二个数组
        //最大堆存的元素是<Pair>，此时元素的大小关系为pair对象中u+v的值越大，认为元素越大【最大堆大的先出就达到最后剩和最小的数对】
        Queue<Pair> queue=new PriorityQueue<>(new Comparator<Pair>() {
            @Override
            public int compare(Pair o1, Pair o2) {
                return (o2.u+o2.v)-(o1.u+o1.v);//输入对象的值越大返回值越小，最小堆是小的先出，相当于本来值大的先出了，达到了最大堆出队的效果
            }
        });
        //2.遍历两个数组，u来自于第一个数组，v来自于第二个数组
        //重点:k值可能比数组长度大，此时只需要遍历到数组长度就好
        //k<数组长度时，数组取值只用取到k，因为元素按值升序，k后的一定是大值，用不到
        //综合，所以循环的终止条件就是：Math.min(nums.length,k),取键值对个数k与数组长度的较小值【难点】
        for (int i = 0; i < Math.min(nums1.length,k) ; i++) {
            for (int j = 0; j < Math.min(nums2.length,k); j++) {
                if(queue.size()<k){//队列长度<k个键值对数目
                    queue.offer(new Pair(nums1[i],nums2[j]));//直接入队，u是nums1[i],v是nums2[j]
                }else{
                    int add=nums1[i]+nums2[j];//当前数对的大小和
                    Pair pair=queue.peek();//取得堆顶元素
                    if(add>(pair.u+ pair.v)){
                        //当前数组大于堆顶，无需入队
                        continue;
                    }else{
                        queue.poll();
                        queue.offer(new Pair(nums1[i],nums2[j]));
                    }
                }
            }
        }
        //此时优先级队列中就存储了和最小的前k个Pair对象 每个小list就是一个数对
        List<List<Integer>> ret=new ArrayList<>();
        //注意：k>数组长度时，可能还没走到k已经出队完了，所以要加上不为空的循环条件
        for (int i = 0; i < k && (!queue.isEmpty()); i++) {
            List<Integer> temp=new ArrayList<>();
            Pair pair=queue.poll();
            temp.add(pair.u);
            temp.add(pair.v);
            ret.add(temp);
        }
        return ret;
    }
}
